package com.hqq.leetcode.dp;

/**
 * UniquePaths 不同的路径
 * Description:
 * A robot is located at the top-left corner of a m x n grid.
 * The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.
 * How many possible unique paths are there?
 * <p>
 * Input:
 * m = 3,n = 3;
 * m = 4,n = 5;
 * Output:
 * 6
 * 35
 * <p>
 * Created by heqianqian on 2017/9/15.
 */
public class UniquePaths {

    public static void main(String[] args) {
        UniquePaths up = new UniquePaths();
        int result = up.uniquePaths4(3, 3);
        System.out.println(result);
        result = up.uniquePaths4(4, 5);
        System.out.println(result);
    }

    /*
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    //使用一维数组的解法
    public int uniquePaths2(int m, int n) {
        // DP with 1 dimension array
        int[] a = new int[n];
        for (int j = 0; j < n; j++) {
            a[j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                a[j] += a[j - 1];
            }
        }
        return a[n - 1];
    }

    //一维数组进阶版
    public int uniquePaths3(int m, int n) {
        // DP with 1 dimension array
        int row = Math.min(m, n);
        int col = Math.max(m, n);
        int[] a = new int[col];
        for (int j = 0; j < col; j++) {
            a[j] = 1;
        }
        for (int i = 1; i < row; i++) {
            a[i] *= 2;
            for (int j = i + 1; j < col; j++) {
                a[j] += a[j - 1];
            }
        }
        return a[col - 1];
    }

    //数学解法
    public int uniquePaths4(int m, int n) {
        double dom = 1;
        double dedom = 1;
        int small = m < n ? m - 1 : n - 1;
        int big = m < n ? n - 1 : m - 1;
        for (int i = 1; i <= small; i++) {
            dedom *= i;
            dom *= small + big + 1 - i;
        }
        return (int)(dom/dedom);
    }
}
